package club.vann.nowcoder;

/**
 * <p>难度：Medium</p>
 * <p>题目：寻找第K大的数</p>
 * <p>描述：有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
 *
 * 给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。
 *
 * 示例1
 * 输入
 * 复制
 * [1,3,5,2,2],5,3
 * 返回值
 * 复制
 * 2</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-18:19:49:47
 */
public class NC88 {
    public static void main(String[] args) {
        NC88 nc88 = new NC88();

        System.out.println("Result["+TestCase.ANS+"] : " + nc88.findKth(TestCase.A, TestCase.N, TestCase.K));
    }

    /**
     * 解法一：
     *
     * @param a
     * @param n
     * @param K
     * @return
     */
    public int findKth(int[] a, int n, int K) {
        // write code here
        // 借助快速排序思路

        return findK(a, n, 0, n-1, K);
    }

    private int findK(int[] a,int n, int low, int high, int K) {
        if(low <= high) {
            int mid = findMid(a, low, high);
            if(mid == n-K) {
                return a[mid];
            } else if(mid < n-K) {
                return findK(a, n, mid+1, high, K);
            } else {
                return findK(a, n, low, mid-1, K);
            }
        }
        return -1;
    }

    /**
     * 返回基准位置的索引。
     *
     * @return
     */
    private int findMid(int[] a, int low, int high) {
        int mid = a[low];
        while(low < high) {
            while(low < high && mid <= a[high]) {
                high --;
            }
            a[low] = a[high];

            while(low < high && a[low] <= mid) {
                low ++;
            }
            a[high] = a[low];
        }
        a[low] = mid;
        return low;
    }

    static class TestCase {
        public static int ANS = 2;
        public static int[] A = {1,3,5,2,2};
        public static int N = 5;
        public static int K = 3;
    }
}
